Adaptive inexact fast augmented Lagrangian methods for constrained convex optimization

摘要

In this paper we analyze several inexact fast augmented Lagrangian methodsfor solving linearly constrained convex optimization problems. Mainly, ourmethods rely on the combination of excessive-gap-like smoothing techniquedeveloped in [15] and the newly introduced inexact oracle framework from [4].We analyze several algorithmic instances with constant and adaptive smoothingparameters and derive total computational complexity results in terms ofprojections onto a simple primal set. For the basic inexact fast augmentedLagrangian algorithm we obtain the overall computational complexity of order$\mathcal{O}\left(\frac{1}{\epsilon^{5/4}}\right)$, while for the adaptivevariant we get $\mathcal{O}\left(\frac{1}{\epsilon}\right)$, projections onto aprimal set in order to obtain an $\epsilon-$optimal solution for our originalproblem.